1. Field of the Invention
The present invention relates to a network analyzing method for performing a delay analysis of a network having false paths and for optimizing the network.
There are many issues concerning networks that transmit information and goods. In particular, the issues of minimizing delays in a network or of restricting them to be as small as possible are important. Generally, there are two types of delays, one of which is an arrival time that is calculated from an input node of the network therethrough, the other of which is a required time that is calculated at an output node of the network.
An electric circuit is constructed of semiconductor devices that are connected by leads. Thus, when the semiconductor devices are treated as nodes, the electric circuit can be treated as a network.
A computer is constructed of functional elements that are connected by information transmission paths. When the functional elements are treated as nodes, the computer can be treated as a network.
A communication system is constructed of terminal units and exchanges that are connected with lines. When the terminal units and exchanges are treated as nodes, the communication system can be treated as a network.
A physical distribution system is constructed of collection and delivery stations that are connected by transportation paths such as roads. When the collection and delivery stations are treated as nodes, the physical distribution system can be treated as a network.
In the aforementioned networks, as delays in the networks are shortened, the values of information or goods transmitted are proportionally increased.
2. Description of the Prior Art
To analyze delays in a network having nodes a to q connected by arrow edges (directional lines), two methods are known.
In the first method, referring to FIG. 1, the arrival time at a node i (where i is a to q) is represented by T(i). The input time of the node i is given by the following inequalities.
(a) i /.epsilon. Inputs (in the case that the node i is not an input node of the network; where /.epsilon. is the negation of .epsilon.) EQU T(i).gtoreq.max{T(j)+delay(j, i)}j .epsilon. fanin(j) PA1 (b) i .epsilon. Inputs (in the case that the node i is an input node of the network) EQU T(i)=Tstart(i) PA1 (c) i .epsilon. Outputs (in the case that the node i is an output node of the network) EQU T(i).ltoreq.Tend(i) (1) PA1 (a) The false paths should be physically present as connections between nodes in the network. PA1 (b) The false paths do not actually or substantially transmit information, goods, or the like from an input node to an output node of the paths as a network operation.
Inputs represents a set of input nodes of the network. Outputs represents a set of output nodes of the network. fanin(i) represents a set of nodes that supply inputs to node i. delay(j, i) represents a delay time from the node j to the node i. Initial time Tstart(i) is given to each input node. An allowable maximal arrival time Tend(i) is given to each output node.
For a required time t(i), the similar relation is given by the following inequalities. ##STR1## where fanout(i) represents a set of nodes that supply outputs of the node i.
Since the above formulas can be expressed with linear inequalities, such restrictions can be replaced with linear or non-linear programming problems, thereby optimizing various networks.
In the second method, a network shown in FIG. 2 is scanned from an input node to an output node so as to determine an arrival time T. An initial time is given to the input node (in this example, the initial time is 0). Iterate the following operation while there exists a node which is not given an arrival time: select a node whose all fanin nodes are already given an arrival time, then find the highest value of {(the arrival time of the fannin node)+(the delay time from the fanin node to this node)}, and give this node the highest value as its arrival time. This operation is equivalent to an expression where the sign of inequality of the formula (1) (a) is substituted with an equal sign. For example, the arrival time at the node d on the path connected to the node h (namely, 0+1=1) is compared with the arrival time at the node d on the path connected to the node c (namely, 2+1=3). Thus, the arrival time 3 is selected. To obtain a required time, an initial time is given to each output node. Thereafter, the network is scanned from the output side to the input side.
General networks may have false paths. The false paths should satisfy the following conditions.
A typical example of a false path is a redundant path compared with a bypass. In the network shown in FIG. 2, when a path of a.fwdarw.b.fwdarw.c.fwdarw.d.fwdarw.e.fwdarw.f.fwdarw.g has a delay of 6, if the delay needs to be reduced, a node k as shown in FIG. 3 may be placed in the network so as to bypass the path of a.fwdarw.b.fwdarw.c.fwdarw.d.fwdarw.e.fwdarw.f.fwdarw.g with a path of a.fwdarw.k.fwdarw.g. In other words, since information travels the path of a.fwdarw.k.fwdarw.g earlier than the path of a.fwdarw.b.fwdarw.c.fwdarw.d.fwdarw.e.fwdarw.f.fwdarw.g, the latter path becomes a false path. However, a false path does not mean an unnecessary path. When one of the edges on the false path is removed, the path of h.fwdarw.g or the path of a.fwdarw.j is disconnected. Thus, by removing edges, false paths cannot be removed. The maximum delay path of the chart is apparently the path of a.fwdarw.b.fwdarw.c.fwdarw.d.fwdarw.e.fwdarw.f.fwdarw.g. However, in consideration of the network operation, the maximum delay path is a.fwdarw.k.fwdarw.g.
In large networks, such false paths sometimes occur due to bypasses that are placed intentionally by network designers. However, false paths may be mistakenly placed in a network designing process.
In the conventional delay analyzing method, a network is defined on a chart, so that a maximum path on the chart is obtained. Thus, in the conventional method, due to the presence of false paths, correct delays cannot be obtained. In addition, when false paths are removed, other paths may be removed. Thus, correct delays may not be obtained. Consequently, the conventional method cannot deal with networks having false paths.